/*
 * @Author: lei
 * @Description: 希尔排序
 * @FilePath: /new/shellsort.cc
 */

#include <iostream>

#include "sort.h"
using namespace std;
void ShellSort(vector<int>& v) {
  int len = v.size(), tmp, i, j;
  for (int gap = len / 2; gap > 0; gap /= 2) {
    // 每一趟采用插入排序
    for (i = gap; i < len; i++) {
      tmp = v[i];
      for (j = i; j >= gap && tmp < v[j - gap]; j -= gap) {
        v[j] = v[j - gap];
      }
      v[j] = tmp;
    }
  }
}
// int main() {
//   vector<int> v{1, 8, 3, 89, 0, -342, 90, -87, 89, 987, 6};
//   for (auto& t : v) cout << t << " ";
//   cout << endl;
//   ShellSort(v);
//   for (auto& t : v) cout << t << " ";
//   cout << endl;
//   return 0;
// }

// 希尔排序本质上是对插入排序的一种优化，它利用了插入排序的简单，又克服了插入排序每次只交换相邻两个元素的缺点。